package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/">N 叉树的最大深度(Maximum Depth of N-ary Tree)</a>
 * <p>给定一个 N 叉树，找到其最大深度。
 * <p>最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。</p>
 * <p>N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,3,2,4,null,5,6]
 *                       1
 *                     / | \
 *                    3  2  4
 *                   / \
 *                  5   6
 *      输出：3
 *
 * 示例 2：
 *      输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 *                           1
 *                      /  |   |  \
 *                     2   3   4   5
 *                        / \  |  / \
 *                       6  7  8 9  10
 *                          |  |
 *                          11 12
 *                          |
 *                          14
 *      输出：5
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树的深度不会超过 1000 。</li>
 *     <li>树的节点数目位于 [0, 10^4] 之间。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0104DepthOfBinaryTree_S 二叉树的最大深度(Maximum Depth of Binary Tree)
 * @see LC0559MaximumDepthOfNaryTree_S N 叉树的最大深度(Maximum Depth of N-ary Tree)
 * @since 2023/5/23 10:10
 */
public class LC0559MaximumDepthOfNaryTree_S {

    public int maxDepth(Node root) {
        //return maxDepthByIterator(root);
        return maxDepthByRecursion(root);
    }

    private int maxDepthByIterator(Node root) {
        if (root == null) {
            return 0;
        }
        int maxDepth = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node currNode;
            for (int i = 0; i < size; i++) {
                currNode = queue.poll();
                if (currNode != null) {
                    for (Node child : currNode.children) {
                        queue.offer(child);
                    }
                }
            }
            ++maxDepth;
        }
        return maxDepth;
    }

    private int maxDepthByRecursion(Node root) {
        if (root == null) {
            return 0;
        }
        int sumMaxDepth = 0;
        if (root.children != null) {
            for (Node child : root.children) {
                sumMaxDepth = Math.max(sumMaxDepth, maxDepthByRecursion(child));
            }
        }
        return sumMaxDepth + 1;
    }

    static class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1, new ArrayList<>());
        Node node1 = new Node(3, new ArrayList<>());
        Node node2 = new Node(2, new ArrayList<>());
        Node node3 = new Node(4, new ArrayList<>());
        Node node4 = new Node(5, new ArrayList<>());
        Node node5 = new Node(6, new ArrayList<>());
        List<Node> children1 = new ArrayList<>();
        children1.add(node1);
        children1.add(node2);
        children1.add(node3);
        List<Node> children2 = new ArrayList<>();
        children2.add(node4);
        children2.add(node5);
        node.children = children1;
        node1.children = children2;
        LC0559MaximumDepthOfNaryTree_S lc0559MaximumDepth_OfNaryTree_s = new LC0559MaximumDepthOfNaryTree_S();
        System.out.println(lc0559MaximumDepth_OfNaryTree_s.maxDepth(node));
    }
}
